/*
 * jngc, Java utility classes by Nicholas Coltharp
 * Copyright (C) 2010 Nicholas Coltharp <ngc1@rice.edu>
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

package edu.rice.ngc1.util.function;

import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
import java.util.concurrent.Callable;

import edu.rice.ngc1.util.annotation.Immutable;
import edu.rice.ngc1.util.annotation.Immutable.Strictness;
import edu.rice.ngc1.util.annotation.Tuple;
import edu.rice.ngc1.util.tuple.Tuple2;
import edu.rice.ngc1.util.tuple.Tuple3;

/**
 * Utility class containing various higher-order functions for use
 * with the {@link Executable} interface.
 */
public final class Executables {

    /**
     * Private constructor to prevent construction.
     */
    private Executables() {}

    /**
     * Exception thrown to "break" from any of this class's iterating
     * methods.
     */
    private static final class StopIterationException extends RuntimeException {

        private static final long serialVersionUID = -8401250985060918552L;
    }

    /**
     * The null function, which always returns {@code null}.
     */
    @Immutable(Strictness.MAX)
    private static final class NullFunction implements
            SafeExecutable<Object, Object> {

        private NullFunction() {}

        public static final NullFunction SINGLE = new NullFunction();

        @Override
        public Object exec(Object arg) {
            return null;
        }
    }

    /**
     * Returns an {@code Executable} which always returns {@code null}
     * .
     * 
     * @param <P>
     *            the type of object that the returned object will
     *            receive
     * @param <R>
     *            the type of object that the returned executable is
     *            expected to return
     * @return an {@link Executable} which always returns {@code null}
     */
    @SuppressWarnings("unchecked")
    public static <P, R> SafeExecutable<P, R> getNullFunction() {
        return ((SafeExecutable<P, R>) NullFunction.SINGLE);
    }

    /**
     * The identity function, which always returns the object provided
     * as its argument.
     */
    @Immutable(Strictness.MAX)
    private static final class IdentityFunction implements
            SafeExecutable<Object, Object> {

        private IdentityFunction() {}

        public static final IdentityFunction SINGLE = new IdentityFunction();

        @Override
        public Object exec(Object arg) {
            return arg;
        }
    }

    /**
     * Returns an {@link Executable} which always returns the argument
     * given to it.
     * 
     * @param <T>
     *            the type of object which this executable will
     *            receive
     * @return an {@link Executable} which always returns the argument
     *         given to it
     */
    @SuppressWarnings("unchecked")
    public static <T> SafeExecutable<T, T> getIdentityFunction() {
        return ((SafeExecutable<T, T>) IdentityFunction.SINGLE);
    }

    /**
     * The false predicate, which always returns {@code false}.
     */
    @Immutable(Strictness.MAX)
    private static final class FalsePredicate implements SafePredicate<Object> {

        private FalsePredicate() {}

        public static final FalsePredicate ONLY = new FalsePredicate();

        @Override
        public Boolean exec(Object arg) {
            return false;
        }
    }

    /**
     * Returns a {@link Predicate} which always returns {@code false}.
     * 
     * @param <T>
     *            the type of parameter which the returned predicate
     *            will take
     * @return a {@link Predicate} which always returns {@code false}
     */
    @SuppressWarnings("unchecked")
    public static <T> SafePredicate<T> getFalsePredicate() {
        return ((SafePredicate<T>) FalsePredicate.ONLY);
    }

    /**
     * The true predicate, which always returns {@code true}.
     */
    @Immutable(Strictness.MAX)
    private static final class TruePredicate implements SafePredicate<Object> {

        private TruePredicate() {}

        public static final TruePredicate SINGLE = new TruePredicate();

        @Override
        public Boolean exec(Object arg) {
            return true;
        }
    }

    /**
     * Returns a {@link Predicate} which always returns {@code true}.
     * 
     * @param <T>
     *            the type of parameter which the returned predicate
     *            will take
     * @return a {@link Predicate} which always returns {@code true}
     */
    @SuppressWarnings("unchecked")
    public static <T> SafePredicate<T> getTruePredicate() {
        return ((SafePredicate<T>) TruePredicate.SINGLE);
    }

    /**
     * The and predicate, which ANDs two operations.
     */
    @Tuple({2})
    @Immutable(Strictness.MAX)
    private static final class AndPredicate implements
            Predicate<Tuple2<Callable<Boolean>, Callable<Boolean>>, Exception> {

        private AndPredicate() {}

        public static final AndPredicate SINGLE = new AndPredicate();

        @Override
        public Boolean exec(Tuple2<Callable<Boolean>, Callable<Boolean>> arg)
                throws Exception {
            return (arg.v1.call() && arg.v2.call());
        }
    }

    /**
     * Returns a predicate which will AND the results of two
     * {@code Callable}s.
     * 
     * @return a {@code Predicate} which ANDs two operations
     */
    public static
            Predicate<Tuple2<Callable<Boolean>, Callable<Boolean>>, Exception>
            getAndPredicate() {
        return AndPredicate.SINGLE;
    }

    /**
     * The or predicate, which ORs two operations.
     */
    @Tuple({2})
    @Immutable(Strictness.MAX)
    private static final class OrPredicate implements
            Predicate<Tuple2<Callable<Boolean>, Callable<Boolean>>, Exception> {

        private OrPredicate() {}

        public static final OrPredicate SINGLE = new OrPredicate();

        @Override
        public Boolean exec(Tuple2<Callable<Boolean>, Callable<Boolean>> arg)
                throws Exception {
            return (arg.v1.call() || arg.v2.call());
        }
    }

    /**
     * Returns a predicate which will OR the results of two
     * {@code Callable}s.
     * 
     * @return a {@code Predicate} which ORs two operations
     */
    public static
            Predicate<Tuple2<Callable<Boolean>, Callable<Boolean>>, Exception>
            getOrPredicate() {
        return OrPredicate.SINGLE;
    }

    /**
     * Returns a predicate which will return the opposite of the
     * {@code Boolean} provided to it.
     */
    @Immutable(Strictness.MAX)
    private static final class NotPredicate implements SafePredicate<Boolean> {

        private NotPredicate() {}

        public static final NotPredicate SINGLE = new NotPredicate();

        @Override
        public Boolean exec(Boolean arg) {
            return (!arg);
        }
    }

    /**
     * Returns a predicate which will return the opposite of its
     * argument.
     * 
     * @return a predicate which NOTs its argument
     */
    public static SafePredicate<Boolean> getNotPredicate() {
        return NotPredicate.SINGLE;
    }

    /**
     * Implementation of the {@code Callable} interface which wraps an
     * {@code Executable}. This object represents an "invocation" of
     * an Executable, because it is constructed with the argument
     * which will be passed to the Executable.
     * 
     * @param <P>
     *            the {@code Executable}'s parameter type
     * @param <R>
     *            the return type
     */
    private static final class Invocation<P, R> implements Callable<R> {

        /**
         * The {@code Executable} that this object's
         * {@link java.util.concurrent.Callable#call()} method will
         * execute.
         */
        private final Executable<P, R, ? extends Exception> f;

        /**
         * The argument that will be passed to this object's
         * Executable.
         */
        private final P arg;

        /**
         * Constructs a new {@code Invocation}.
         * 
         * @param f
         *            the {@code Executable} to call
         * @param arg
         *            the argument to pass to the executable
         */
        public Invocation(Executable<P, R, ? extends Exception> f, P arg) {
            this.f = f;
            this.arg = arg;
        }

        /**
         * Calls this object's executable with its given argument.
         * 
         * @return the result of the executable's
         *         {@link Executable#exec(java.lang.Object)} method
         * @throws Exception
         *             if the {@code Executable} throws an exception
         */
        @Override
        public R call() throws Exception {
            return f.exec(arg);
        }
    }

    /**
     * Returns a {@code Callable} which, when called, will execute the
     * given {@code Executable} with the given parameter.
     * 
     * @param <P>
     *            the parameter type
     * @param <R>
     *            the return type
     * @param f
     *            the {@code Executable} to call
     * @param arg
     *            the argument to pass to the given {@code Executable}
     * @return a new {@code Callable} which will execute the given
     *         {@code Executable}
     */
    public <P, R> Callable<R> toCallable(
            Executable<P, R, ? extends Exception> f, P arg) {
        return new Invocation<P, R>(f, arg);
    }

    /**
     * When called from inside an {@code Executable} that is being
     * used by one of this class's iterating methods, this method
     * causes the iteration to cease and the method to return. Will
     * result in undefined behavior if called anywhere else.
     */
    public static void stopIteration() {
        throw new StopIterationException();
    }

    /**
     * The {@code map} executable.
     * 
     * @param <P>
     *            the type of element in the parameter iterable
     * @param <R>
     *            the type of element in the result iterable
     * @param <E>
     *            type of exception that may be thrown
     */
    @Immutable(Strictness.MAX)
    @Tuple({2})
    private static final class Map<P, R, E extends Throwable> implements
            Executable<Tuple2<Executable<P, R, E>, Iterable<P>>, List<R>, E> {

        private Map() {}

        public static final Map<Object, Object, Throwable> SINGLE =
                new Map<Object, Object, Throwable>();

        @Override
        public List<R> exec(Tuple2<Executable<P, R, E>, Iterable<P>> arg)
                throws E {
            List<R> ret = new ArrayList<R>();
            try {
                for (P p : arg.v2) {
                    ret.add(arg.v1.exec(p));
                }
            } catch (StopIterationException e) {}
            return ret;
        }
    }

    /**
     * Returns an executable which performs the higher-order function
     * {@code map}. The executable applies a function to every element
     * in an {@code Iterable} and returns a list containing the
     * results. Calling {@link Executables#stopIteration()} will cause
     * an immediate return of the current set of results.
     * 
     * @param <P>
     *            the element type of the input list
     * @param <R>
     *            the element type of the returned list
     * @param <E>
     *            type of exception that may be thrown
     * @return the {@code map} executable
     */
    @SuppressWarnings("unchecked")
    public <P, R, E extends Throwable>
            Executable<Tuple2<Executable<P, R, E>, Iterable<P>>, List<R>, E>
            getMap() {
        return (Map<P, R, E>) Map.SINGLE;
    }

    /**
     * Applies the function returned by {@link #getMap()} to the given
     * parameters.
     * 
     * @param <P>
     *            the input type
     * @param <R>
     *            the output type
     * @param <E>
     *            type of exception that may be thrown
     * @param f
     *            the function to apply
     * @param c
     *            a collection containing inputs to {@code f}
     * @return an array containing the result of applying {@code f} to
     *         every element in {@code c}
     * @throws Exception
     *             if {@code f} ever throws an error
     */
    @SuppressWarnings("unchecked")
    public static <P, R, E extends Throwable> List<R> map(
            Executable<P, R, E> f, Iterable<P> c) throws E {

        return ((Map<P, R, E>) Map.SINGLE)
                .exec(new Tuple2<Executable<P, R, E>, Iterable<P>>(f, c));
    }

    @Tuple({2})
    public static final class Filter<T, E extends Throwable> implements
            Executable<Tuple2<Predicate<T, E>, Iterable<T>>, List<T>, E> {

        private Filter() {}

        public static final Filter<Object, Throwable> SINGLE =
                new Filter<Object, Throwable>();

        @Override
        public List<T> exec(Tuple2<Predicate<T, E>, Iterable<T>> arg) throws E {
            List<T> ret = new ArrayList<T>();
            try {
                for (T t : arg.v2) {
                    if (arg.v1.exec(t)) {
                        ret.add(t);
                    }
                }
            } catch (StopIterationException e) {}
            return ret;
        }
    }

    /**
     * The higher-order function {@code filter}. Returns an array
     * containing every element in {@code c} for which {@code f}
     * returns {@code true}.
     * 
     * @param <T>
     *            the type of {@code c}'s elements
     * @param <E>
     *            type of exception that may be thrown
     * @param f
     *            a predicate to apply to every element in {@code c}
     * @param c
     *            a collection containing the inputs to {@code f}
     * @return an array containing every element in {@code c} for
     *         which {@code f} returns {@code true}
     * @throws Exception
     *             if {@code f} ever throws an error
     */
    @SuppressWarnings("unchecked")
    public static <T, E extends Throwable> List<T> filter(Predicate<T, E> f,
            Iterable<T> c) throws E {

        return ((Filter<T, E>) Filter.SINGLE)
                .exec(new Tuple2<Predicate<T, E>, Iterable<T>>(f, c));
    }

    @Immutable(Strictness.MAX)
    @Tuple({2, 3})
    public static final class Fold<P, R, E extends Throwable>
            implements
            Executable<Tuple3<Executable<Tuple2<R, P>, R, E>, Iterable<P>, R>, R, E> {

        @Override
        public
                R
                exec(Tuple3<Executable<Tuple2<R, P>, R, E>, Iterable<P>, R> arg)
                        throws E {
            R r = arg.v3;

            try {
                for (P p : arg.v2) {
                    r = arg.v1.exec(new Tuple2<R, P>(r, p));
                }
            } catch (StopIterationException e) {}

            return r;
        }
    }

    /**
     * The higher-order function {@code fold}. The given function is
     * applied cumulatively, starting with the given initial value and
     * the first element of the given list, and with each subsequent
     * operation using the result of the previous operation and the
     * next element in the list.
     * 
     * @param <P>
     *            the input type
     * @param <R>
     *            the output type
     * @param f
     *            the function to apply
     * @param c
     *            a collection containing the elements to operate on
     * @param init
     *            the initial value to provide to {@code f}
     * @return the result of applying {@code f} cumulatively to all of
     *         the elements in {@code c}
     * @throws Exception
     *             if {@code f} ever throws an error
     */
    public static <P, R, E extends Throwable> R fold(
            Executable<Tuple2<R, P>, R, E> f, Collection<P> c, R init) throws E {
        R r = init;

        try {
            for (P p : c) {
                r = f.exec(new Tuple2<R, P>(r, p));
            }
        } catch (StopIterationException e) {}

        return r;
    }

    /**
     * Creates a new function which is the combination of two other
     * functions.
     * 
     * @param <T>
     *            the ultimate parameter type
     * @param <U>
     *            the "intermediate" type: the parameter type of
     *            {@code f} and the return type of {@code g}
     * @param <V>
     *            the ultimate return type
     * @param f
     *            the first function
     * @param g
     *            the second function
     * @return a new function {@code h} such that {@code h(x)} is
     *         equivalent to {@code f(g(x))}
     */
    @SuppressWarnings("unchecked")
    public static <T, U, V, E1 extends Throwable, E2 extends Throwable>
            Executable<T, V, Throwable> compose(final Executable<U, V, E1> f,
                    final Executable<T, U, E2> g) {
        return ((Compose<T, U, V, E1, E2>) Compose.SINGLE)
                .exec(new Tuple2<Executable<U, V, E1>, Executable<T, U, E2>>(f,
                        g));
    }

    @Tuple({2})
    @Immutable(Strictness.MAX)
    private static final class Compose<T, U, V, E1 extends Throwable, E2 extends Throwable>
            implements
            SafeExecutable<Tuple2<Executable<U, V, E1>, Executable<T, U, E2>>, Executable<T, V, Throwable>> {

        private Compose() {}

        public static final Compose<Object, Object, Object, Throwable, Throwable> SINGLE =
                new Compose<Object, Object, Object, Throwable, Throwable>();

        @Override
        public Executable<T, V, Throwable> exec(
                final Tuple2<Executable<U, V, E1>, Executable<T, U, E2>> arg) {
            return new Executable<T, V, Throwable>() {

                @Override
                public V exec(T innerArg) throws Throwable {
                    return arg.v1.exec(arg.v2.exec(innerArg));
                };
            };
        }
    }

    /**
     * Checks whether a given predicate ever tests {@code true} for
     * any element in a given collection. This method will
     * automatically return once the given predicate returns
     * {@code true}. Calling {@link #stopIteration()} will make this
     * method return {@code false}.
     * 
     * @param <T>
     *            the type of object contained in {@code c}
     * @param f
     *            the test to run on each element
     * @param c
     *            the set of elements to iterate over
     * @return {@code true} if {@code f} ever returns {@code true};
     *         {@code false} otherwise
     * @throws Exception
     *             if {@code f} ever throws an error
     */
    public static <T, E extends Throwable> boolean isEverTrue(
            Predicate<T, E> f, Collection<T> c) throws E {
        try {
            for (T t : c) {
                if (f.exec(t)) {
                    return true;
                }
            }
        } catch (StopIterationException e) {}
        return false;
    }

    /**
     * Finds the first element in a collection for which a given
     * predicate returns {@code true}.
     * 
     * @param <T>
     *            the type that {@code c} contains
     * @param f
     *            a predicate to execute for every element in
     *            {@code f}
     * @param c
     *            the collection to check every element in
     * @return the first element in {@code c} for which {@code f}
     *         returns {@code true}, or {@code null} if no such
     *         element exists or if {@link #stopIteration()} is called
     * @throws Exception
     *             if {@code f} ever throws an exception
     */
    public static <T, E extends Throwable> T find(Predicate<T, E> f,
            Collection<T> c) throws E {
        try {
            for (T t : c) {
                if (f.exec(t)) {
                    return t;
                }
            }
        } catch (StopIterationException e) {}
        return null;
    }
}
